package com.fireway;

import java.util.NoSuchElementException;

/**
 * 基于双向链表的双端链表
 * 2018年 05月 18日 星期五
 *
 * @author fireway
 */
public class DoublyLinkedList<E> {
    private Entry<E> mHeader;  // Pointer to first node

    private Entry<E> mTailer;  // Pointer to last node

    private int mSize = 0;

    public DoublyLinkedList() {
        mHeader = null;
        mTailer = null;
    }

    public void addFirst(E e) {
        Entry<E> newEntry = new Entry<E>(e);

        if (empty()) {
            mTailer = newEntry;
        } else {
            mHeader.mPrev = newEntry;
        }

        newEntry.mNext = mHeader;
        mHeader = newEntry;
        mSize++;
    }

    public void addLast(E e) {
        Entry<E> newEntry = new Entry<E>(e);

        if (empty()) {
            mHeader = newEntry;
        } else {
            mTailer.mNext = newEntry;
            newEntry.mPrev = mTailer;
        }

        mTailer = newEntry;
        mSize++;
    }

    public E removeFirst() {
        if (empty()) {
            throw new NoSuchElementException();
        } else {
            Entry<E> tmp = mHeader;

            if (null == mHeader.mNext) {
                mTailer = null;
            } else {
                mHeader.mNext.mPrev = null;
            }
            mHeader = mHeader.mNext;
            mSize--;

            E result = tmp.mElement;
            return result;
        }
    }

    public E removeLast() {
        if (empty()) {
            throw new NoSuchElementException();
        } else {
            Entry<E> tmp = mTailer;

            if (null == mTailer.mPrev) {
                mHeader = null;
            } else {
                mTailer.mPrev.mNext = null;
            }
            mTailer = mTailer.mPrev;
            mSize--;

            E result = tmp.mElement;

            return result;
        }
    }

    public void add(int index, E element) {
        if (0 == index) {
            addFirst(element);
        } else {
            addBefore(element, entry(index));
        }
    }

    private void addBefore(E element, Entry<E> current) {
        Entry<E> newEntry = new Entry<E>(element);
        newEntry.mNext = current;
        newEntry.mPrev = current.mPrev;
        current.mPrev.mNext = newEntry;
        current.mPrev = newEntry;
        mSize++;
    }

    public int indexOf(Object o) {
        int index = 0;
        for (Entry<E> e = mHeader; e != null ; e = e.mNext) {
            if (isEqual(o, e.mElement)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    public E get(int index) {
        return entry(index).mElement;
    }

    private Entry<E> entry(int index) {
        if (index < 0 || index >= mSize) {
            throw new IndexOutOfBoundsException("Index: " + index+ ", Size: " + mSize);
        }

        Entry<E> current = null;
        if (index < (mSize >> 1)) {
            current = mHeader;
            for (int i = 0; i < index; i++) {
                current = current.mNext;
            }
        } else {
            current = mTailer;
            for (int i = mSize - 1; i > index; i--) {
                current = current.mPrev;
            }
        }
        return current;
    }

    public boolean remove(Object o) {
        Entry<E> current = mHeader;

        while (current != null) {
            if (isEqual(o, current.mElement)) {
                break;
            }
            current = current.mNext;
        }

        if (current == mHeader) {
            mHeader = current.mNext;
            current.mNext.mPrev = null;
        } else if (current == mTailer) {
            current.mPrev.mNext = null;
            mTailer = current.mPrev;
        } else if (null == current) {
            return false;
        } else {
            current.mPrev.mNext = current.mNext;
            current.mNext.mPrev = current.mPrev;
        }

        current.mNext = current.mPrev = null;
        current.mElement = null;
        current = null;
        mSize--;

        return true;
    }

    private boolean isEqual(Object o1, Object o2) {
        if (null == o1) {
            return o2 == null;
        } else {
            return o1.equals(o2);
        }
    }

    public boolean empty() {
        return null == mHeader && null == mTailer;
    }

    public int size() {
        return mSize;
    }

    public void displayForward() {
        System.out.print("List (first-->last): [");
        Entry<E> current = mHeader;
        while(current != null) {
            E e = current.mElement;
            System.out.print(e);
            if (current.mNext != null) {
                System.out.print(" ");
            }
            current = current.mNext;
        }
        System.out.print("]\n");
    }

    public void displayBackward() {
        System.out.print("List (last-->first): [");
        Entry<E> current = mTailer;
        while(current != null) {
            E e = current.mElement;
            System.out.print(e);
            if (current.mPrev != null) {
                System.out.print(" ");
            }
            current = current.mPrev;
        }
        System.out.print("]\n");
    }

    private static class Entry<E> {
        E mElement;
        Entry<E> mPrev;
        Entry<E> mNext;

        public Entry(E element) {
            mElement = element;
        }
    }
}
